package org.usmile.algorithms.knapsack;

public class _0_1_Knapsack2 {
    private int[] weights;
    private int[] values;

    public int solve(int[] weights, int[] values, int capacity) {
        this.weights = weights;
        this.values = values;

        return dfs(-1, capacity);
    }

    private int dfs(int parent, int capacity) {
        int max = 0;
        for (int i = parent + 1; i < weights.length; i++) {
            if (weights[i] > capacity) {
                continue;
            }
            max = Math.max(max, dfs(i, capacity - weights[i]));
        }

        return parent == -1 ? max : max + values[parent];
    }

    public static void main(String[] args) {
        _0_1_Knapsack2 k = new _0_1_Knapsack2();
        int[] w = {3, 4, 5, 2};
        int[] v = {15, 10, 12, 8};
        System.out.println(k.solve(w, v, 10));
    }
}
